package 中等.并查集;

/**
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，
 * 并将这些区域里所有的 'O' 用 'X' 填充。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/surrounded-regions/
 */
public class 被围绕的区域_130 {

    public static void main(String[] args) {

        solve(new char[][]{
                {'O', 'X', 'O', 'O', 'O', 'X'},
                {'O', 'O', 'X', 'X', 'X', 'O'},
                {'X', 'X', 'X', 'X', 'X', 'O'}});

    }

    /**
     * 并查集
     * 将边界上的 O 全部连接到一个虚拟节点上面
     * 然后将整个矩阵中的 O 连通起来，最后遍历
     * 一遍每个节点，如果和虚假节点连通的，就是 O 否则是 X
     *
     * @param board
     */
    public static void solve(char[][] board) {
        int dummyNode = board.length * board[0].length;
        DSU dsu = new DSU(dummyNode + 1);

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O') {
                    int curNode = i * board[i].length + j;
                    if (i == 0 || i == board.length - 1 || j == 0 || j == board[0].length - 1) {
                        dsu.union(curNode, dummyNode);
                    }

                    // 上方的 O 连通
                    if (i - 1 >= 0 && board[i - 1][j] == 'O') {
                        dsu.union(curNode, (i - 1) * board[0].length + j);
                    }
                    // 右方的 O 连通
                    if (j + 1 < board[0].length && board[i][j + 1] == 'O') {
                        dsu.union(curNode, i * board[0].length + j + 1);
                    }
                }
            }
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (!dsu.connected(i * board[0].length + j, dummyNode)) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    static class DSU {

        private int[] pre;

        public DSU(int n) {
            pre = new int[n];
            for (int i = 0; i < pre.length; i++) {
                pre[i] = i;
            }
        }

        public int find(int x) {
            if (pre[x] == x) {
                return x;
            }
            return pre[x] = find(pre[x]);
        }

        public void union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return;

            pre[x] = y;
        }

        public boolean connected(int x, int y) {
            return find(x) == find(y);
        }
    }

}
